package demo8;

import lombok.Getter;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * F:/integration/basic/SpringWithGradle-gitee/gradlew.bat :simple-demo:test  --tests "demo8.PermutationForCoinTest.test1" --info -Dorg.gradle.jvmargs="-Xmx3g -Xms1g -verbose:gc"
 */
@Getter
public class PermutationForCoin {
    public PermutationForCoinWithImprove createPermutationForCoinWithImprove(){
        return new PermutationForCoinWithImprove();
    }

    /**
     * using the method is the makeup of the table
     * index=0  indicate 25
     * index=1  indicate 10
     * index=2  indicate 5
     * index=3  indicate 1
     */
    public class PermutationForCoinWithImprove {
        String[] tmp = new String[]{"0,0,0,0","0,0,0","0,0","0",""};
        HashSet<String> set = new HashSet<>();
        public void permutationStart(int val) {

            int index = 0;
            int[] denoms = {25, 10, 5, 1};
            ArrayList<String> strings = new ArrayList<>();
            permutation(val, index, denoms,"");
        }

        public void permutation(int remainVal, int index, int[] denoms,String str) {
            if(index==4){ return ;}
            int denomination = denoms[index];

            int countMax = (int) (remainVal / denomination);
            for (int i = countMax; i >= 0; i--) {
                String strNew = new String(str);
                if(remainVal - i * denomination ==0){
                    int length = (str+i+",").split(",").length;
                    if(!set.add((str+i+",")+tmp[length])){
                        throw new RuntimeException("error ,contains duplicate perms. ");
                    }
                    System.out.println("got it !!! , the perms the goals is : "+(str+i+",")+tmp[length]);
                    continue;
                }
                strNew+=(i+",");
                permutation(remainVal - i * denomination, index + 1, denoms,strNew);

            }

            return;
        }


    }

    private int counter;

    public void permutationStart(int val) {
        permutation(val, 0, 0, 0, 0);
    }

    HashSet set = new HashSet<String>();

    /**
     * error: contain the duplicate perms.
     * because of  the duplicate recusion ,
     * start use the count1 or end use the count1,
     */
    public void permutation(int val, int count25, int count10, int count5, int count1) {
        String detail = String.format("count25: %s,count10: %s,count5: %s,count1: %s", count25, count10, count5, count1);

        int sum = count25 * 25 + count10 * 10 + count5 * 5 + count1;
        if (val == sum) {
            if (!set.add(detail)) {
                // stop it
                System.out.println(detail);
            }
            counter++;
            System.out.println("got it is equal, each count is: " + detail);
            return;
        }
        if (val < sum) {
//            System.out.println("the permutation "+sum+" is > "+val);
            return;
        }
        permutation(val, count25 + 1, count10, count5, count1);
        permutation(val, count25, count10 + 1, count5, count1);
        permutation(val, count25, count10, count5 + 1, count1);
        permutation(val, count25, count10, count5, count1 + 1);
        return;
    }
}

